package practise;

import java.util.Stack;

public class IsSubtree {

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(subRoot == null) {
            return true;
        }
        if(root == null) {
            return false;
        }
        return isSameTree(root, subRoot)
                || isSameTree(root.right, subRoot)
                ||  isSameTree(root.left, subRoot);

    }

    public  boolean isSameTree(TreeNode p, TreeNode q) {

        Stack<TreeNode> pStack = new Stack<>();
        Stack<TreeNode> qStack = new Stack<>();
        TreeNode pTmp, qTmp;
        pStack.push(p);
        qStack.push(q);

        while(!pStack.isEmpty() && !qStack.isEmpty()) {
            pTmp = pStack.pop();
            qTmp = qStack.pop();
            if(pTmp == null && qTmp == null) {
                continue;
            }
            if(qTmp == null || pTmp == null) {
                return false;
            }
            if(pTmp.val != qTmp.val) {
                return false;
            }
            pStack.push(pTmp.left);
            pStack.push(pTmp.right);
            qStack.push(qTmp.left);
            qStack.push(qTmp.right);
        }
        return pStack.isEmpty() && qStack.isEmpty();
    }
}
